from leetcode.utils.treenode import TreeNode


def build_tree(preorder, inorder):
    if len(inorder) == 0:
        return
    ind = inorder.index(preorder[0])
    tree = TreeNode(preorder[0])
    tree.left = build_tree(preorder[1: ind + 1], inorder[: ind])
    tree.right = build_tree(preorder[ind + 1:], inorder[ind + 1:])
    return tree


if __name__ == '__main__':
    preorder = [3,9,20,15,7]
    inoreder = [9,3,15,20,7]
    res = build_tree(preorder, inoreder)
